package com.lw.leetcode.bit.b;

/**
 * Created with IntelliJ IDEA.
 * b
 * bit
 * 1915. 最美子字符串的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/6 19:01
 */
public class WonderfulSubstrings {

    public static void main(String[] args) {
        WonderfulSubstrings test = new WonderfulSubstrings();

        // 9
        String str = "aabb";

        // 4
//        String str = "aba";
        long l = test.wonderfulSubstrings(str);
        System.out.println(l);
    }

    public long wonderfulSubstrings(String word) {
        long[] arr = new long[1024];
        int item = 0;
        arr[0] = 1;
        int length = word.length();
        long count = 0;
        for (int i = 0; i < length; i++) {
            item ^= (1 << (word.charAt(i) - 'a'));
            count += arr[item];
            for (int j = 0; j < 10; j++) {
               count += arr[(1<< j) ^ item];
            }
            arr[item]++;
        }
        return count;
    }

}
